1. Field of the Invention
The present invention relates to systems and methods for allocating and scheduling resources to satisfy one or more time critical objectives. More specifically, the present invention relates to systems and methods for automatically allocating and scheduling weapon system to threats such that a pre-specified battle-space engagement objective is optimized.
2. Description of the Related Art
Previous approaches for automatically allocating and scheduling defensive weapons against attacking threats to maximize an engagement objective have only addressed the static target-weapon pairing problem which is to determine the optimal allocation of weapon systems to engage threats.
While some of these approaches have used trial-intercept calculations to determine the window of engagement to determine a weapon system""s effectiveness against a threat, they do not address the issue of when to deploy the weapon system against the threat in this window. This decision is typically made by the individual weapon systems after threats have been assigned to it by the target-weapon pairing algorithm.
Thus, the previous approaches are based on a sequential two-step decision process. In the first step, the target-weapon pairing algorithm decides on which threat(s) to assign to a weapon system based on their effectiveness measures. In the second step, each weapon system makes its decision about when to deploy and engage threat(s) assigned to it from the first step.
Since the first step did not model the engagement-time resource requirements and temporal constraints of the weapon systems, there is a possibility that this step may have assigned enough threats to a weapon system to overwhelm its time-dependant resources, possibly rendering some of the threats unengageable. For example, certain weapon systems have ground-based sensors that guide the interceptor towards the threat either from launch to impact or during some part of the interceptor""s flight (seeker on the interceptor may guide during remaining part of flight). Since the number of such ground-based sensors is limited, a weapon system can only guide a limited number of interceptors at any time. If the number of threats requiring simultaneous guidance exceeds this number, then the weapon system will not be able to engage all its threats. The weapon system may then inform the operator about the situation and the operator may then pass it to another weapon system, possibly resulting in delay and even leaked threats.
This sequential disconnected decision making process has two disadvantages:
(1) since actual weapon resource requirements have not been modeled in the first step, weapon systems may end up being assigned more threats than they can engage, and,
(2) consequently, there may be engagement delays and/or leaked threats (sub-optimal engagement).
There are several U.S. patents in the area of automatic weapon assignment against threats. See, for example, U.S. Pat. No. 5,992,288 issued Nov. 30, 1999 to Gregory R. Barnes and entitled Knowledge Based Automatic Threat Evaluation And Weapon Assignment. This patent evaluates threats and based on trial-intercept calculations determines which weapon systems can engage it and ranks them based on their effectiveness in neutralizing a threat. The algorithm selects the best weapon to neutralize the threat. No optimization across the battle-space is provided.
See also U.S. Pat. No. 5,511,218 issued Apr. 23, 1996 to P. Castelaz and entitled Connectionist Architecture For Weapons Assignment; U.S. Pat. No. 5,404,516 issued Apr. 04, 1995 to D. E. Georgiades, P. R. Jensen and T. S. Nichols and entitled System For Allocating Resources And Method; and U.S. Pat. No. 5,153,366 issued Oct. 06, 1992 to T. Lucas and entitled Method For Allocating And Assigning Defensive Weapons Against Attacking Weapons. As discussed before, none of these inventions optimize the deployment or launch time of the weapon system. U.S. Pat. No. 5,404,516 incorporates the temporal dimension in an embodiment that deals with assigning jamming resources to assist in missions attacking enemy assets, where each mission has a predetermined weapon allocation to threat, weapon loading, etc. This assumes that the time of engagement between a threat and weapon (of a mission) is predetermined (i.e., fixed) and the jammer is supposed to be available to jam from this time up to a fixed future time (10 minutes). Each jammer supports a set of missions. While the allocation of jammers to support missions is optimized to maximize an objective function, there is no optimization of the jamming time itself as the start time and duration are fixed. Thus the reference assumes fixed resource allocation and only determines the scheduling of available resources such that no resources overlap in time. In other words, it does allocation and scheduling without optimizing the temporal dimension.
In short, none of these patents address and solve the problem of optimizing xe2x80x9cwhenxe2x80x9d to deploy the resources (weapon systems). Some of these approaches use a simple weapon model to perform trial-intercept calculations (battle-space analysis). The weapon model used includes weapon system parameters such as weapon system location, type of interceptor, range of interceptor, etc. that determine if and when the weapon system will be able to engage and intercept a specific threat. All weapon systems that can potentially engage a threat become options for engaging that threat. However, weapon system resource limitations during actual engagement of the threat when multiple threats are assigned to it are not considered. So if a threat can be intercepted by a weapon system based on battle-space calculations, it is assumed that the weapon system will be able to engage and intercept it.
These approaches do not determine whether the weapon system can actually engage the threats if several threats are assigned to this weapon system with each threat individually engagable by the weapon system based on battle-space calculations. For example, if several threats have overlapping intercept time windows and each interceptor needs to be guided during some part of its flight from launch to intercept, then there may not be enough guidance sensors at this weapon system to guide interceptors to engage all threats assigned to it. Thus, every threat may end up being assigned a weapon system in these methods, but every threat may actually not be engaged as its assigned weapon system may not have enough resources at engagement time. As a consequence, they suffer from the disadvantages listed above. Even if engagement time resources are considered in the allocation and scheduling, as in U.S. Pat. No. 5,404,516, optimal engagement objectives cannot be achieved without optimizing the time of allocation (scheduling) of these resources.
Hence, a need remains in the art for a weapon allocation system and method that determines weapon allocation and scheduling to optimize an objective function while simultaneously incorporating and optimizing the temporal dimension.
The need in the art is addressed by the system and method for automatic weapon allocation and scheduling of the present invention. The inventive method includes the steps of providing data with respect to threats, weapons, weapon allocation options; weapon allocation rules; and temporally dependent constraints with respect thereto; evaluating the data; and temporally allocating the weapons to the threats automatically in accordance with the evaluation.
The current invention computes the optimal pairing and the best time to deploy each weapon system against threat(s) it is paired with in arriving at the pairing. This results in an optimal assignment where weapon resource constraints are not exceeded and therefore guarantee availability of sufficient resources for engagement of every threat that is paired with a weapon system.
The invention overcomes the disadvantages of previous approaches by combining the first and second steps typical of the prior art into a single decision step. Thus, it determines not only which threats to assign to a weapon system but also when to deploy them (launch interceptors) so that a pre-specified engagement objective is optimized. This requires modeling the weapon time-dependent resource constraints during the assignment evaluation itself. By calculating the best combination of deployment times as part of the allocation decision itself in evaluating a particular assignment, it can determine whether the assignment would have resulted in a situation where each weapon system would have been able to engage all its threats or not. As a result, it can achieve an optimal assignment where all weapon systems will actually be able to engage threats assigned to them. This will result in effective battle management even under extremely heavy attack situations that seemingly outnumber weapon resources.
However, combination of the two steps introduces temporal dimension optimization into the asset allocation problem causing a combinatorial explosion in the solution space and resulting in a resource-constrained scheduling problem i.e., a Weapon Allocation and Scheduling problem (WASE). This is a far-more computationally expensive problem than the static problem tackled in previous approaches. Since one of the primary objectives is to have a system that runs in close to real time (i.e., update times of at most few seconds), we have developed a fast algorithm to solve the WASE problem. The novel algorithm is a hybrid genetic algorithm that uses a true genetic algorithm and merges it with a simulated-annealing type algorithm. The engagement objective in the genetic algorithm is posed as a function of the deployment times that are optimized by the simulated-annealing type algorithm. Thus, by optimizing the deployment or launch times in this step, the objective function of each trial assignment in the genetic algorithm is optimized. The genetic algorithm then optimizes the engagement objective by searching for the best assignment.
A novel heuristic measure in a temporal optimization algorithm is also disclosed that provides a fast, but approximately optimal solution with significant reduction in the computational cost.